/* trie.c */

#include <windows.h>

struct Trie{
    DWORD dwSize;
    DWORD dwUsed;
    LPVOID lpvData;
};

struct Trie TrieCreate(){
    struct Trie trie;
    trie.dwSize = 32;
    trie.dwUsed = 0;
    trie.lpvData = malloc(32 << 7);
    RtlZeroMemory(trie.lpvData, 1 << 7);
    return trie;
}

static DWORD TrieCreateNode(struct Trie* pTrie){
    if((++pTrie->dwUsed) >= pTrie->dwSize){
        pTrie->dwSize <<= 1;
        pTrie->lpvData = realloc(pTrie->lpvData, pTrie->dwSize << 7);
    }
    RtlZeroMemory((LPBYTE)pTrie->lpvData + (pTrie->dwUsed << 7), 1 << 7);
    return pTrie->dwUsed;
}

LPVOID TrieInsert(struct Trie* pTrie, LPCSTR lpszStr){
    LPVOID lpvCurrent = pTrie->lpvData;
    DWORD dwIndex;

    for(dwIndex = 0; lpszStr[dwIndex]; dwIndex++){
        LPDWORD lpdwIndex = (LPDWORD)lpvCurrent + (lpszStr[dwIndex] - 'a' + 1);

        if(*lpdwIndex == 0){
            *lpdwIndex = TrieCreateNode(pTrie);
        }
        lpvCurrent = (LPBYTE)pTrie->lpvData + (*lpdwIndex << 7);
    }
    return (LPBYTE)pTrie->lpvData + ((*(LPDWORD)lpvCurrent ? *(LPDWORD)lpvCurrent : (*(LPDWORD)lpvCurrent = TrieCreateNode(pTrie))) << 7);
}

LPVOID TrieQuery(struct Trie* pTrie, LPCSTR lpszStr){
    LPVOID lpvCurrent = pTrie->lpvData;
    DWORD dwIndex;

    for(dwIndex = 0; lpszStr[dwIndex]; dwIndex++){
        LPDWORD lpdwIndex = (LPDWORD)lpvCurrent + (lpszStr[dwIndex] - 'a' + 1);

        if(*lpdwIndex == 0){
            return NULL;
        }
        lpvCurrent = (LPBYTE)pTrie->lpvData + (*lpdwIndex << 7);
    }
    return *(LPDWORD)lpvCurrent ? (LPBYTE)pTrie->lpvData + (*(LPDWORD)lpvCurrent << 7) : NULL;
}

void TrieDelete(struct Trie* pTrie){
    free(pTrie->lpvData);
    pTrie->lpvData = NULL;
}
